package LanQiao;

import java.util.Scanner;

public class demo4 {
    /**
     * 快速排序递归实现
     */

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] q = new int[n];
        for (int i = 0; i < n; i++) {
            q[i] = scanner.nextInt();
        }

        quickSort(q, 0, n - 1);

        for (int i = 0; i < n; i++) {
            System.out.print(q[i] + " ");
        }
    }

    static void quickSort(int[] q, int l, int r) {
        if (l >= r)
            return;
        int i = l, j = r, temp = q[l];      //选取左边的第一个数作为基准
        while (i < j) {
            while (q[j] >= temp && i < j)     //处理右边
                j--;
            q[i] = q[j];    //右边出现比基准小的数，放到左边，左边第一个数已经作为基准存储到temp中
            while (q[i] <= temp && i < j)     //处理左边
                i++;
            q[j] = q[i];      //左边出现比基准大的数，放到右边
        }
        //此时 i = j，将基准放回原数组
        q[i] = temp;
        //递归遍历左侧和右侧
        quickSort(q, l, i - 1);
        quickSort(q, i + 1, r);
    }
}

